\documentclass[a4paper,10pt]{article}

\usepackage{ifpdf}
\ifpdf
    \usepackage{cmap}
\fi

\usepackage[utf8]{inputenc}
\usepackage[T2A]{fontenc}
\usepackage[russian]{babel}
\usepackage{listings}
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2cm]{geometry}

\usepackage{amsmath, amssymb}



\begin{document}
\lstset{language=C++,inputencoding=utf8}

\section*{Билет \No 3.5}
{\em Метапрограммирование. Шаблоны и Generics. 
Частичная специализация шаблонов.}

\section{Метапрограммирование} 
{\bf Метапрограммирование}~--- создание программ, которые создают другие программы как результат своей работы (либо — частный случай —
изменяющие или дополняющие себя во время выполнения).

Метапрограммирование можно разделить на 2 направления: на {\it стадии компиляции (генерация кода)} и на {\it стадии выполнения
(самомодифицирующийся код).}

Первое направление позволяет получить программу при меньших затратах времени и усилий, чем если бы программист писал её вручную. Второе~---
расширяет возможности программиста.

\subsection{Генерация кода}

При этом подходе код программы не пишется вручную, а создается автоматически программой-ге\-не\-ра\-то\-ром на основе другой, более простой
программы.

Такой подход приобретает смысл, если при программировании вырабатываются различные дополнительные правила (более высокоуровневые парадигмы,
выполнение требований внешних библиотек, стереотипные методы реализации определенных функций и пр.). При этом часть кода теряет
содержательный смысл и становится лишь механическим выполнением правил. Когда эта часть становится значительной, возникает мысль задавать
вручную лишь содержательную часть, а остальное добавлять автоматически. Это и проделывает генератор.

Реализуется 2 основными методами:
\begin{enumerate}
   \item Шаблоны (наиболее известные случаи применения~--- препроцессор {\tt C} и шаблоны в {\tt C++}).
      Решают задачу, если соблюдение «правил» сводится к вставке в программу повторяющихся (или почти повторяющихся) кусков кода. Помимо
      этого, обладают еще рядом достоинств: например, помогают повторному использованию.

   \item Внешнеязыковые средства (пример: генераторы синтаксических и лексических анализаторов {\tt lex}, {\tt yacc}, {\tt bison}).
    Применяются в случаях, если простых средств вроде шаблонов недостаточно. Язык генератора составляется так, чтобы автоматически или с
    минимальными усилиями со стороны программиста реализовывать правила парадигмы или необходимые специальные функции. Фактически, это~--- 
    более высокоуровневый язык программирования, а генератор~---  не что иное, как транслятор. Генераторы пишутся, как правило, для создания
    специализированных программ, в которых очень значительная часть стереотипна, либо для реализации сложных парадигм (таких, как паттерны
    проектирования).
\end{enumerate}


\subsection{Самомодифицирующийся код}
Возможность изменять или дополнять себя во время выполнения превращает программу в виртуальную машину. Хотя такая возможность существовала
уже давно на уровне машинных кодов (и активно использовалась, например, при создании полиморфных вирусов), с метапрограммированием обычно
связывают перенос подобных технологий в высокоуровневые языки.

Основные методы реализации:
\begin{enumerate}
   \item  Интроспекция~--- представление внутренних структур языка в виде переменных встроенных типов с возможностью доступа к ним из
      программы.  Позволяет во время выполнения смотреть, создавать и изменять определения типов, стек вызовов, обращаться к переменной по
      имени, получаемому динамически и пр.
        
   \item Пространство имён {\tt System.Reflection} и тип {\tt System.Type} в {\tt .NET}; классы {\tt Class}, {\tt Method}, {\tt Field} в
      {\tt Java}; представление пространств имен и определений типов через встроенные типы данных в {\tt Python}; стандартные встроенные
      возможности в {\tt Forth} по доступу к ресурсам виртуальной машины.

   \item Интерпретация произвольного кода, представленного в виде строки.
      \begin{itemize}
         \item Существует естественным образом во множестве интерпретируемых языков, например {\tt eval()} в {\tt PHP}.
         \item  Для {\tt C++} есть библиотека, позволяющая «на лету» компилировать и генерировать исполняемый код (используется
            урезанный компилятор {\tt gcc}).
         \item Для {\tt Forth} использования процедуры интерпретации из строки {\tt EVALUATE}.
      \end{itemize}
\end{enumerate}
   
Принципиальный недостаток технологий этого направления~--- неприменимость к компилируемым языкам. Можно ввести в такой язык интерпретатор,
как в вышеуказанной библиотеке для {\tt С++}, но это практически сведет на нет главное преимущество данных языков~--- производительность. Хороший
задел, компиляции программы при загрузке, сравнимый с {\tt С} демонстрируют удачные реализации Forth языка. 

\section{Шаблоны и Generics}
Обобщённое программирование~--- это парадигма программирования, заключающаяся в написании алгоритмов, которые можно применять к различным
типам данных. В том или ином виде поддерживается разными языками программирования. Возможности обобщённого программирования впервые
появились в 70-х годах в языках {\tt CLU} и {\tt Ada}, а затем во многих объектно-ориентированных языках, таких как {\tt C++}, {\tt Java},
{\tt D} и языках для платформы {\tt .NET}.

\subsection{Шаблоны}
В языке C++ обобщённое программирование основывается на понятии «шаблон», обозначаемом ключевым словом template.
{\small \begin{lstlisting}
// returns maximum of two elements
template <typename T> T max(T x, T y)
{
    if (x < y)
        return y;
    else
        return x;
}
\end{lstlisting}}

Интересное применение нашли шаблоны в языке {\tt C++}. Оказалось, что шаблоны в этом языке являются тьюринг-полным функциональном языком. Другими
словами на шаблонах {\tt С++} можно написать программу, реализующую произвольный алгоритм, и эта программа выполнится в момент компиляции. К
примеру, можно посчитать  50-е число Фибоначчи. Тогда во время выполнения программы не придется тратить время на его вычисления. Одной
интересной особенностью такого программирования на шаблонах, является встроенный механизм {\it мемоизации} (сохранения результата вычисления
функции). Это значит, что рекурсивный алгоритм для вычисления $k$-го числа Фибоначчи работающий «в лоб» сделает порядка $k$ операций (вместо
ожидаемых $2^k$). 
{\small \begin{lstlisting}
template <int i> struct fib
{
   static const int val = fib<i - 1>::val + fib<i - 2>::val;
};

template <> struct fib<1>
{
   static const int val = 1;
};

template <> struct fib<2>
{
   static const int val = 1;
};

int main()
{
   std::cout << fib<20>::val;
}
\end{lstlisting}}

Но это не самое интересное: программирование на шаблонах {\tt С++} позволяет общаться с типом как с обычным объектом. К примеру,
можно составить список типов, удалить из него все встроенные типы, а из оставшегося списка создать объект, который будет унаследован от всех
типов из данного списка. Для такого метапрограммирования была написана специальная библиотека {\tt MPL} {\it (MetaProgramming Library)}.

\subsection{Generics}
Язык {\tt Java} предоставляет средства обобщённого программирования, синтаксически основанные на {\tt C++}. 
В {\tt Java} {\bf generics} (параметризованные типы или родовые типы) имеют мнимое сходство с шаблонами {\tt C++} как по синтаксису, так и по
ожидаемому месту их применения (например, в качестве контейнерных классов). Но это сходство только поверхностное~--- родовые типы в языке
программирования {\tt Java} почти полностью реализуются в компиляторе, который выполняет проверку типов и выявление типа {\it (type inference)} и,
затем, генерирует обычные не параметризованные байткоды. Такая техника реализации, называемая {\it стиранием} (когда компилятор использует
информацию о родовом типе для контроля типов и удаляет ее перед генерированием байткода), имеет неожиданные, а иногда и непонятные
последствия. В то время как родовые типы являются большим шагом на пути к безопасности {\tt Java}-классов, изучение их использования почти
наверняка будет вызывать некоторую озадаченность (а иногда и мучения).

\section{Частичная специализация шаблонов}
Если у шаблона класса есть несколько параметров, то можно специализировать его только для одного или нескольких аргументов, оставляя другие
неспециализированными. Иными словами, допустимо написать шаблон, соответствующий общему во всем, кроме тех параметров, вместо которых
подставлены фактические типы или значения. Такой механизм носит название частичной специализации шаблона класса. Она может понадобиться при
определении реализации, более подходящей для конкретного набора аргументов.

Рассмотрим шаблон класса {\tt Screen}. Частичная специализации {\tt Screen<hi,80>} дает более эффективную реализацию для экранов с 80
столбцами:
{\small\begin{lstlisting}
template <int hi, int wid>
class Screen {
};

template <int hi>
class Screen<hi, 80> {
public:
   Screen();
   // ...
private:
   string            screen;
   string::size_type cursor;
   short             height;
};
\end{lstlisting}}

Частичная специализация шаблона класса~--- это шаблон, и ее определение похоже на определение шаблона. Список параметров здесь отличается от
соответствующего списка параметров общего шаблона. Для частичной специализации шаблона Screen есть только один параметр-константа hi,
поскольку значение второго аргумента равно 80, т.\,е. в данном списке представлены только те параметры, для которых фактические аргументы еще
неизвестны.
Имя частичной специализации совпадает с именем того общего шаблона, которому она соответствует, в нашем случае {\tt Screen}. Однако за ее именем
всегда следует список аргументов.  

\end{document}
